package com.example.schoolblog.blog.zsf;




public class Tree {
    public static void main(String[] args) {
        int[] a = {5,5};
        //System.out.println(right_bound(a,7));
        Solution solution = new Solution();
        System.out.println(solution.search(a, 6));

    }
    static int right_bound(int[] nums, int target) {
        if (nums.length == 0) return -1;
        int left = 0, right = nums.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                left = mid + 1; //细节点
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;//细节点
            }
        }
        if(left == 0) return -1;
        if(left == nums.length &&  nums[left - 1] != target) return -1;
        return left - 1;
    }
}
class Solution {
    public int search(int[] nums, int target) {
        // 搜索右边界 right
        int i = 0, j = nums.length - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] <= target) i = m + 1;
            else j = m - 1;
        }
        int right;
        if(j == -1 || nums[j] != target)  right = -1;
        else right = j;
        //搜索左边界
        i = 0; j = nums.length - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] < target) i = m + 1;
            else j = m - 1;
        }
        int left;
        if(i == nums.length || nums[i] != target) left = -1;
        else left = i;

        if(left == -1 && right == -1){
            return 0;
        }
        return right - left + 1;
    }
}
